import java.util.Arrays;
class Solution {

    private Map<String, Integer> countMap = new HashMap<>();

    public List<Integer> findSubstring(String s, String[] words) {
        this.countMap.clear();
        for (String word : words) {
            int count = this.countMap.getOrDefault(word, 0);
            count++;
            this.countMap.put(word, count);
        }
        List<Integer> ans = new ArrayList<>();
        int length = words[0].length() * words.length;
        for (int i = 0; i + length <= s.length(); i++) {
            String subStr = s.substring(i, i + length);
            if (strMatch(subStr, words)) {
                ans.add(i);
            }
        }
        return ans;
    }
    private boolean strMatch(String s, String[] words) {
        int wordLength = words[0].length();
        Map<String, Integer> countMap = new HashMap<>(words.length);
        for (int i = 0; i < s.length(); i+=wordLength) {
            String word = s.substring(i, i+wordLength);
            int count = countMap.getOrDefault(word, 0);
            count++;
            countMap.put(word, count);
        }
        return mapEquals(countMap, this.countMap);
    }

    private boolean mapEquals(Map<String, Integer> map1, Map<String, Integer> map2) {
        if (map1.size() != map2.size()) {
            return false;
        }
        for (Map.Entry<String, Integer> entry : map1.entrySet()) {
            if(!entry.getValue().equals(map2.get(entry.getKey()))) {
                return false;
            }
        }
        return true;
    }
}
